class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        p = s
        n = len(p)
        s = s[::-1]
        next_p = [-1] * n
        for i in range(1, n):
            j = next_p[i - 1]
            while j != -1 and p[j + 1] != p[i]:
                j = next_p[j]
            if p[j + 1] == p[i]:
                next_p[i] = j + 1
        i = 0
        j = 0
        while i < n:
            if p[j] == s[i]:
                i += 1
                j += 1
            else:
                if j > 0:
                    j = next_p[j - 1]
                else:
                    j = -1
                while j != -1 and p[j + 1] != s[i]:
                    j = next_p[j]
                j += 1
                if p[j] == s[i]:
                    i += 1
                    j += 1
                else:
                    i += 1
        t = ''
        for k in range(-1, j - n - 1, -1):
            t += p[k]
        t += p
        return t


data = Solution()
s = "abcd"
print(data.shortestPalindrome(s))
s = "ba"
print(data.shortestPalindrome(s))
s = "aacecaaa"
print(data.shortestPalindrome(s))